package algorithms.leaning.class22;

import common.util.MyUtil;

/**
 * 给定一个正数n，求n的裂开方法数，
 * 规定：后面的数不能比前面的数小
 * 比如4的裂开方法有：
 * 1+1+1+1、1+1+2、1+3、2+2、4
 * 5种，所以返回5
 *
 * @author guichang
 * @date 2021/6/24
 */

@SuppressWarnings("all")
public class Code3_动态规划_数分裂 {

    public static void main(String[] args) {
        // 2 1+1 2
        // 3 1+1+1 1+2 3
        // 5 1+1+1+1+1 1+1+1+2 1+1+3 1+4 1+2+2 2+3 5
        for (int i = 1; i <= 13; i++) {
            MyUtil.printf("{}-{}", i, ways(i));
        }
    }

    public static int ways(int n) {
        if (n <= 0) {
            return 0;
        }
        return process(1, n);
    }

    /**
     * 当前来到了index，rest数的裂开方法数
     *
     * @param index 当前位置，从1开始递增
     * @param rest  裂开基准
     * @return 方法数
     */
    private static int process(int index, int rest) {
        if (rest == 0) {
            return 1;
        }
        if (rest < index) {
            return 0;
        }
        int ways = 0;
        for (int i = 0; i * index <= rest; i++) {
            ways += process(index + 1, rest - i * index);
        }
        return ways;
    }

}